#define _CRT_SECURE_NO_WARNINGS
class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int key = nums.size() - 1;
        int ret = 0;
        for (key; key >= 2; key--) {
            int right = key - 1;
            int left = 0;

            while (left < right) {
                if (((nums[right] + nums[left]) > nums[key]))
                {
                    ret += (right - left);
                    right--;
                }
                else
                    left++;
            }
        }
        return ret;
    }
};